package exercise01;

import java.util.ArrayList;
import java.util.List;

// 子集
class Solution1 {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < (1 << n); i ++) {
            List<Integer> sub = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                // n = 3
                // 000 001 010 011 100 101 110 111
                // 空   a   b   ab  c   ac  bc  abc
                if (((i >> j) & 1) == 1)
                    sub.add(nums[j]);
            }
            result.add(sub);
        }
        return result;
    }
}

public class Day230702 {
    List<List<Integer>> result = new ArrayList<>();
    ArrayList<Integer> sub = new ArrayList<>();
    int[] arr;
    public List<List<Integer>> subsets(int[] nums) {
        arr = nums;
        for (int k = 0; k <= nums.length; k++) {
            // 0~n 个数的 组合
            dfs(k, 0);
        }
        return result;
    }
    private void dfs(int k, int cur) {
        if (sub.size() == k) {
            result.add(new ArrayList(sub));
            return;
        }
        for (int i = cur; i < arr.length; i++) {
            sub.add(arr[i]);
            dfs(k, i + 1);
            sub.remove(sub.size() - 1);
        }
    }
}

// 组合
// 深度优先
class Solution2 {
    List<List<Integer>> result = new ArrayList<>();
    ArrayList<Integer> sub = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        dfs(n ,k , 1);
        return result;
    }

    private void dfs(int n, int k, int cur) {
        if (sub.size() == k) {
            result.add(new ArrayList<>(sub));
            return;
        }
        for (int i = cur; i <= n; i++) {
            sub.add(i);
            dfs(n, k, i + 1);
            sub.remove(sub.size() - 1);
        }
    }
}
